package com.zlp.mybatis;

import org.junit.Test;

import java.util.*;

/**
 * @Author: zhulaiping
 * @Date: 2021/6/29 9:02
 */
public class Algorithm {
    public String convertToTitle(int num) {
        StringBuilder ret = new StringBuilder();
        char ch;
        do{
            if(num%26==0) ch = 'Z';
            else ch = (char) ((num%26)+64);
            ret.insert(0,ch);
            num /= 26;
        }while (num>1);
        return ret.toString();
    }



    char[] arr;
    int i;
    public String countOfAtoms(String formula) {
        arr = formula.toCharArray();
        LinkedList<Map<String,Integer>>stack = new LinkedList<>();
        stack.push(new HashMap<>());
        while (i<formula.length()){
            if(arr[i]=='('){
                i++;
                stack.push(new HashMap<>());
            }else if(arr[i]==')'){
                i++;
                int num = parseNum();
                Map<String, Integer> map = stack.pop();
                Map<String, Integer> map2 = stack.peek();
                for(Map.Entry<String,Integer> entry:map.entrySet()){
                    String key = entry.getKey();
                    int value = entry.getValue();
                    //entry.setValue(value*num);
                    map2.put(key,map2.getOrDefault(key,0)+value*num);
                }
            }else {
                String key = new String(new char[]{arr[i++]});
                key += parseString();
                int num = parseNum();
                Map<String,Integer> map = stack.peek();
                map.put(key,map.getOrDefault(key,0)+num);
            }
        }
        Map<String,Integer>treeMap = new TreeMap<>(stack.pop());
        StringBuilder sb = new StringBuilder();
        for(Map.Entry entry:treeMap.entrySet()){
            int value = (int) entry.getValue();
            sb.append(entry.getKey()+""+(value==1?"":value));
        }
        return sb.toString();
    }

    private int parseNum() {
        StringBuilder sb = new StringBuilder();
        while (i<arr.length&&Character.isDigit(arr[i])){
            sb.append(arr[i++]);
        }
        return sb.toString().equals("")?1:Integer.valueOf(sb.toString());
    }

    private String parseString() {
        StringBuilder sb = new StringBuilder();
        while (i<arr.length&&arr[i]>='a'&&arr[i]<='z'){
            sb.append(arr[i++]);
        }
        return sb.toString();
    }

    @Test
    public void  gg(){
        //[["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
            String[] s1 = new String[]{"David","3","Ceviche"};
            String[] s2 = new String[]{"Corina","10","Beef Burrito"};
            String[] s3 = new String[]{"David","3","Fried Chicken"};
            String[] s4 = new String[]{"Carla","5","Water"};
            String[] s5 = new String[]{"Carla","5","Ceviche"};
            String[] s6 = new String[]{"Rous","3","Ceviche"};
            List<List<String>>list = new ArrayList<>();
            list.add(Arrays.asList(s1));
            list.add(Arrays.asList(s2));
            list.add(Arrays.asList(s3));
            list.add(Arrays.asList(s4));
            list.add(Arrays.asList(s5));
            list.add(Arrays.asList(s6));
            displayTable(list);
    }

    public List<List<String>> displayTable(List<List<String>> orders) {
        Map<String,Integer>orderMap = new HashMap<>();
        Map<String,Integer>xMap = new TreeMap<>();
        Map<Integer,Integer>yMap = new TreeMap<>();
        for (List<String> list:orders){
            String key = list.get(2)+"-"+list.get(1);
            orderMap.put(key,orderMap.getOrDefault(key,0)+1);
            xMap.put(list.get(2), 0);
            yMap.put(Integer.valueOf(list.get(1)),0);
        }

        List<List<String>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        ret.get(0).add("Table");
        int i=1,j=1;
        for (Map.Entry<String,Integer>entry:xMap.entrySet()){
            entry.setValue(i++);
            ret.get(0).add(entry.getKey());
        }
        for (Map.Entry<Integer,Integer>entry:yMap.entrySet()){
            entry.setValue(j);
            ret.add(new ArrayList<>());
            ret.get(j++).add(entry.getKey()+"");
        }
        for (int k=1;k< yMap.size()+1;k++){
            for (int m=0;m<xMap.size();m++){
                ret.get(k).add(""+0);
            }
        }
        for (Map.Entry<String,Integer>entry:orderMap.entrySet()){
            String[] split = entry.getKey().split("-");
            int x = xMap.get(split[0]),y = yMap.get(Integer.valueOf(split[1]));
            ret.get(y).remove(x);
            ret.get(y).add(x,entry.getValue()+"");
        }
        return ret;
    }


    public int countPairs(int[] d) {
        int mod = (int) (1e9+7);
        int maxValue = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for (int num:d)maxValue = Math.max(maxValue,num);
        long ret = 0;
        for (int i=0;i<d.length;i++){
            int value = d[i];
            for (int cur=1;cur<=2*maxValue;cur<<=1){
                if(map.containsKey(cur-d[i])){
                    int count = map.getOrDefault(cur - d[i], 0);
                    ret += count;
                    ret %= mod;
                }
            }
            map.put(d[i],map.getOrDefault(d[i],0)+1);
        }
        return (int) ret;
    }

    @Test public void tt(){
        //countOfAtoms("(H)");
        numSubarraysWithSum(new int[]{1,0,1,0,1},2);
    }
    public int numSubarraysWithSum(int[] nums, int goal) {
        int ret = 0;
        for (int i=1;i<nums.length;i++){
            nums[i] += nums[i-1];
        }
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        for (int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i]-goal)){
                ret += map.get(nums[i]-goal);
            }
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        return ret;
    }

}
